/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年02月27日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/
#include <iostream>
#include<vector>

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int size = nums.size();
        if( size == 0 ){
            return false;
        }

        int sum = 0;
        for(int i = 0; i < size; i++){
            sum += nums[i];
        }

        if(sum & 1){
            return false;
        }

        int target = sum >> 1;
        vector<vector<bool>> dp(size, vector<bool>(target+1, false));
        if( nums[0] <= target ){
            dp[0][nums[0]] = true;
        }

        for(int i = 1; i < size; i++){
            for(int j = 0; j <= target; j++){
                dp[i][j] = dp[i-1][j];
                
                if( nums[i] == j){
                    dp[i][j] == true;
                }else if(nums[i] < j){
                    dp[i][j] = (dp[i-1][j] || dp[i-1][j-nums[i]]);
                }
            }
        }

        return dp[size-1][target];

    }
};